\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}

\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 5}

\paragraph{Задание 1.} Докажите непланарность следующих графов:

\begin{itemize}
\item а) $K_5$

\item б) $K_{3,3}$
\end{itemize}

Можно пользоваться только формулой Эйлера

\begin{Solution}
В графе любая грань ограничена не менее чем 3 ребрами, для двудольного графа можно сказать, что не менее чем 4 ребрами, так как все циклы в двудольном графе должны быть четны, тогда можно сказать, что:

\[
	3 \left|\text{Г}\right| \le 2 \left|E\right|
\]

или для двудольного графа:

\[
	2 \left|\text{Г}\right| \le \left|E\right|
\]

Теперь пользуясь полученными неравнествами:
\[
	\left|V\right|-\left|E\right|+\left|\text{Г}\right| = 2 \Rightarrow 3\left|V\right|-3\left|E\right|+2\left|E\right| \ge 6 \Rightarrow \left|E\right| \le 3\left|V\right| - 6
\]

для двудольных графов:

\[
	\left|E\right| \le 2 \left|V\right| - 4
\]

Графы $K_{3,3}$ и $K_5$ не удовлетворяют этим оценкам, следовательно они не планарны.
\end{Solution}

\paragraph{Задание 2.} Докажите, что грани многогранника можно раскрасить в два цвета правильным образом, если и только если в каждой его вершине сходится четное число ребер.

\begin{Solution}
Очевидно, что, если есть вершина с нечетным числом ребер, то окрашивая грани вокруг этой вершины последовательно, покрасить их в два цвета не получится, так как число граней будет нечетным.

Далее заменим многогранник графом следующим образом - каждая грань многогранника вершина графа, если две грани имеют общее ребро, то соответствующие вершины связаны ребром. В полученном графе все грани окружены четным числом ребер (условно грань нового графа - вершина многогранника, количество ребер выходящих из вершины многогранника равно количеству ребер ограничивающих грань полученного графа)

Определим композицию двух пересекающихся циклов следующим образом:
\begin{itemize}
\item если ребро входит в оба цикла, то оно не входит в композицию

\item если ребро входит в один из циклов, то оно принадлежит композиции
\end{itemize}

очевидно, что композиция это также цикл, если исходные циклы не совпадают.

Теперь покажем, что композиция четного цикла и грани полученного выше графа (имеется ввиду цикл образованный ребрами ограничивающими грань) дает четный цикл (если опять же они не совпадают). Допустим, что цикл и грань имеют нечетное число общих ребер, тогда из цикла удалятся эти ребра, но вместо них добавться ребра грани отсутствовашие в первоначальном цикле, которых опять же нечетное число (так как всего ребер ограничивающих грань четное число), следовательно, полученный цикл имеет четное число ребер. В случае, если число общих ребер четно, то из цикла удалится четное число ребер, и добавится четное число ребер (по тем же соображениям), т. е. полученный цикл опять же будет иметь четное число ребер.

Теперь осталось лишь сказать, что в новом графе любой цикл огибает некоторое число граней, и так как композиция всех граней внутри цикла даст четный цикл, то любой цикл в графе четен, следовательно граф двудольный и его можно покрасить в два цвета, а значит и грани исходного многогранника можно покрасить в два цвета нужным образом.
\end{Solution}

\paragraph{Задание 3.} Пусть в графе $G$ $m$ ребер. Докажите, что $\chi \left(G\right) \le \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$.

\begin{Solution}
В крайнем случае каждое ребро в раскрашенном графе связывает разные цвета, т. е. в предельном случае каждое ребро связывает разные пары цветовых компонент графа, таким образом:
\[
	\chi\left(G\right) \left(\chi\left(G\right)-1\right) \le 2m
\]
откуда решая квадратное неравенство получаем требуемое.
\end{Solution}

\paragraph{Задание 4.} Докажите, что:
\begin{itemize}
\item a) $R\left(2; 3, 4\right) \le 9$

\item б) $R\left(2; 3, 5\right) \le 14$

\item в) $R\left(2; 4, 4\right) \le 18$
\end{itemize}

\begin{Solution}
Известна следующая оценка для чисел Рамсея:
\[
	R\left(2; k, m\right) \le R\left(2; k-1, m\right) + R\left(2; k, m-1\right)
\]

Покажем, что в случае, если $R\left(2; k-1, m\right)$ и $R\left(2; k, m-1\right)$ четны, то неравенство становится строгим. Пусть $R\left(2; k-1, m\right) = 2p$ и $R\left(2; k, m-1\right) = 2q$. Возьмем граф из $2p+2q-1$ вершин. Покрасим ребра графа произвольным образом. Выделим в графе вершину $v$, возможны три варианта:
\begin{itemize}
\item $2p$ ребер или более ведущих в $v$ цвета 1. Назовем вершины смежные с $v$ ребрами цвета 1 множеством $M_1$, тогда $\left|M_1\right| = R\left(2; k-1, m\right) = 2p$. Следовательно при любой покраске $M_1$ мы получим либо $m$ ребер цвета 2, и этот случай нам очевидно подходит, либо получим $k-1$ цвета $1$, тогда добавив к ним вершину $v$ получим требуемое.

\item $2q$ ребер или более ведущих $v$ цвета 2. Здесь подходит аналогичное рассуждение.

\item $2p-1$ ребер цвета 1 и $2q-1$ ребер цвета 2. Но такой случай невозможен для всех вершин, так как $\left(2p+2q-1\right)\left(2p-1\right)$ - нечетное число.
\end{itemize}

таким образом получаем, что неравенство строгое, в этом случае:
\[
	\begin{split}
		&R\left(2;3,4\right) < R\left(2;2,4\right) + R\left(2;3,3\right) = 4 + 6 = 10
	\end{split}
\]

Далее пользуясь эти неравенством и оценкой для $R\left(2;3,4\right)$ получаем:

\[
	R\left(2; 3, 5\right) \le R\left(2; 2, 5\right) + R\left(2; 3, 4\right) \le 5 + 9 = 14
\]

и

\[
	R\left(2; 4, 4\right) \le 2 R\left(2; 3, 4\right) \le 18
\]
\end{Solution}

\paragraph{Задание 5.} В графе все вершины имеют степень 3. Докажите, что ребра можно покрасить в два цвета так, чтобы из каждой вершиы выходили ребра обоих цветов.

\begin{Solution}
Найдем в графе наибольшее паросочетание и назовем его $P$. Если оно совершенное, то задача очевидным образом сразу решается, в противном случае рассмотрим вершины не вошедшие в $P$, назовем их $M_1$ и смежные с ними $M_2$. Вершины из $M_1$ не смежны между собой. Каждая вершины из $M_1$ смежна ровно с 3 вершинами из $M_2$, но при этом каждая вершина из $M_2$ смежна роавно с 2 вершинами из $M_1$. Очевидно, что в данном двудольном графе ($M_1$ и $M_2$) каждой вершине из $M_1$ можно найти независимого представителя из $M_2$ (по лемме Холла), назовем это паросочетние $P_2$. Покрасив все ребра $P_1$ и $P_2$ в один цвет, а оставшиеся в другой, получаем требуемую раскраску.
\end{Solution}

\paragraph{Задание 6.} Докажите, что если числа от 1 до 9 покрасить в 2 цвета, то найдется одноцветная арифметическая прогрессия длины 3.

\begin{Solution}
Рассмотрим два случая: 4 и 6 покрашены в один цвет и 4 и 6 покрашены в разный цвет.

Это не важно, но для определенности пусть 4 и 6 покрашены в цвет 1. Тогда чтобы не допустить появления А. П. вершину 5 должны покрасить в цвет 2. Кроме того, чтобы не образовать последовательности 4, 6, 8 или 2, 4, 6, красим 2 и 8 в цвет 2, но тогда получаем последовательность 2, 5, 8 одного цвета.

Теперь пусть 4 и 6 имеют разные цвета, для определенности 4 цвета 1 и 6 цвета 2. Пусть вершина 5 имеет цвет 1 (это опять же не важно, для второго случая доказательство будет полностью аналогичным), тогда чтобы не допустить А. П. 3, 4, 5 красим 3 в цвет 2. Теперь чтобы не допустить А. П. 3, 6, 9 красим 9 в цвет 1. Теперь чтобы избежать А. П. 5, 7, 9, красим 7 в 2, и сразу чтобы не допустить А. П. 6, 7, 8 красим 8 в 1. Теперь чтобы не допустить А. П. 2, 5, 8 красим 2 в 2.

Непокрашеной осталась 1, но при покраске 1 в 1, получаем А. П. 1, 5, 9, а при покраске в 2 получаем А. П. 1, 2, 3.
\end{Solution}

\end{document}
